import random

def random_pick(some_list, probabilities): 
    x = random.uniform(0,1) 
    cumulative_probability = 0.0 
    for item, item_probability in zip(some_list, probabilities): 
        cumulative_probability += item_probability 
        if x < cumulative_probability:
               break 
    return item 

#生成随机游走对象
class R_walk():
    def __init__(self, Graph, walklength, walknumber):
        """
        Graph: item节点图(可以是单向或者双向图)
        walklength: 随机游走的长度
        walknumber: 每个节点随机游走次数
        """
        self.G = Graph
        self.wl = walklength
        self.wn = walknumber
    
    def walk(self, node):
        """
        node: 随机游走的节点
        """
        walk_sequences = []
        for i in range(self.wn):
            walk_sequence = [node]
            tem_node  = node
            for j in range(self.wl):
                if len(self.G[tem_node]) != 0:
                    tem_node = random_pick(self.G[tem_node].keys(), self.G[tem_node].values())
                    walk_sequence.append(tem_node)
                else:
                    break
            if len(walk_sequence)>1:
                walk_sequences.append(walk_sequence)
        return walk_sequences
    
    def random_walk(self):
        random_walk_sequences = []
        nodes = set(self.G.keys())
        for node in nodes:
            random_walk_sequences += self.walk(node)
        return random_walk_sequences